//--------------------------------------------------------------------------------------------------
//                                                   ___  __  __  __  __  __  __  __    __  __  ___ 
// Copyright 2010, Koert van der Veer.              / __)(  )(  )(  \/  )(  )(  )(  )  (  )(  )/ __)
// Licensed under the Apache License,              ( (__  )(__)(  )    (  )(__)(  )(__  )(__)( \__ \
// version 2.0; ("the License")                     \___)(______)(_/\/\_)(______)(____)(______)(___/

// You may not use this file except in compliance with the License.
// You may obtain a copy of the License at 
//     http://www.apache.org/licenses/LICENSE-2.0 
//
// Unless required by applicable law or agreed to in writing, software distributed under the License
// is distributed on an "AS IS" BASIS,  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
// or implied. See the License for the specific language governing permissions and limitations under
// the License. 
//--------------------------------------------------------------------------------------------------
// This file is part of cumulus,  an memory manager implementation in C++.  Details are discussed in
// my blog,  which can be found at http://ondergetekende.nl.  Comments,  suggestions and bug reports
// are welcome. They can be added as comments at the blog. Be advised that in its current form, this
// code is most likely not production ready; it simply hasn't been tested sufficiently. 
//--------------------------------------------------------------------------------------------------
// A generalized doubly linked list with an iterator. 
// The templated ListEntry needs to provide two public pointers to itself: Previous and Next.
// These members needn't be initialized, but they will change while in the list
// ------------------------------------------------------------------------------------------------

#pragma once

namespace Cumulus
{
namespace Utils
{

template< typename ListEntry >
class DoublyLinkedList
{
private:
	// Pointer to the first entry in the list, or NULL if the list is empty
	ListEntry* Head;

	// Pointer to the last entry in the list, or NULL if the lsit is empty
	ListEntry* Tail;

	// The number of elements in the list.
	INT Count;

public:
	class Iterator
	{
		// Implementation details:
		// This iterator will keep a pointer to a list entry at all times. As usual, any 
		// modification to the linked list will invalidate the iterator.
	private:
		// The list being iterated.
		DoublyLinkedList< ListEntry >* List;
		// A pointer to the current entry
		ListEntry* Finger;

		// True if the we're past the end
		bool IsPastEnd;

		// True if we're before the start.
		bool IsPastStart;

		// Returns the current entry in the list, or NULL if we're past the end or before the start
		// of the list.
		ListEntry* GetCurrent() const 
		{
			if( IsPastEnd )
			{
				assert( Finger == List->Tail );
				return NULL;
			}
			else if( IsPastStart )
			{
				assert( Finger == List->Head );
				return NULL;
			}
			else
			{
				return Finger; 
			}
		}

		// Moves the internal pointer to the next item.
		// It is illegal to call IterateNext on an iterator that's already at the end
		void IterateNext()
		{
			// can't iterate further if we're already at the end.
			assert( !IsPastEnd );
			assert( Finger != NULL );
			assert( List != NULL );


			if( IsPastStart )
			{
				// If we're before the start, Finger should already point to the head of the list.
				assert( Finger == List->Head );

				// We're no longer past the start
				IsPastStart = FALSE;
			}
			else
			{
				if( Finger->Next == NULL )
				{
					// Indicate we've passed the end of the list.
					IsPastEnd = TRUE;
				}
				else
				{
					// move the pointer forward.
					Finger = Finger->Next; 
				}
			}
		}

		void IteratePrevious()
		{
			// can't iterate further if we're already at the start.
			assert( !IsPastStart );
			assert( Finger != NULL );
			assert( List != NULL );


			if( IsPastEnd )
			{
				// If we're before the start, Finger should already point to the tail of the list.
				assert( Finger == List->Tail );

				// We're no longer past the end
				IsPastEnd = FALSE;
			}
			else
			{
				if( Finger->Previous == NULL )
				{
					// Indicate we've passed the start of the list
					IsPastStart = TRUE;
				}
				else
				{
					// Move finger to previous item
					Finger = Finger->Previous; 
				}
			}
		}

	public:
		Iterator( )			
			: List( 0 )
			, Finger( NULL )
			, IsPastEnd( TRUE )
			, IsPastStart( TRUE )
		{
		}

		Iterator( DoublyLinkedList< ListEntry >& InList, ListEntry* InFinger )
			: List( &InList)
			, Finger( InFinger )
			, IsPastEnd( Finger == NULL )
			, IsPastStart( Finger == NULL )
		{
			Validate();
		}

		Iterator( const Iterator& Other )
			: List( Other.List )
			, Finger( Other.Finger )
			, IsPastEnd( Other.IsPastEnd )
			, IsPastStart( Other.IsPastStart )
		{
			Validate();
		}

		Iterator& operator =( const Iterator& Other )
		{
			List = Other.List;
			Finger = Other.Finger;
			IsPastStart = Other.IsPastStart;
			IsPastEnd = Other.IsPastEnd;
			return *this;
		}

		// Returns TRUE if the iterator is before the start of the list, e.g. the next item would be the 
		// first item in the list.
		bool IsAtStart() const 
		{ 
			return IsPastStart; 
		}

		// Returns TRUE if the iterator is before the start of the list, e.g. the next item would be the 
		// first item in the list.
		bool IsAtEnd() const 
		{ 
			return IsPastEnd; 
		}

		// Dereference operators
		ListEntry* operator ->() const { return GetCurrent(); }
		ListEntry& operator*() const { return *GetCurrent(); }
		operator ListEntry*() const { return GetCurrent(); }

		// Increment and decrement operators. 
		Iterator& operator++()    
		{ 
			IterateNext(); 
			return *this; 
		}

		Iterator operator++(int) 
		{ 
			Iterator Result(*this);
			IterateNext(); 
			return Result; 
		}

		Iterator& operator--()    
		{ 
			IteratePrevious(); 
			return *this; 
		}
		
		Iterator& operator--(int) 
		{ 
			Iterator Result(*this);
			IteratePrevious(); 
			return Result; 
		}

		// Removes the current item from the list. This operation is only valid if there actually is
		// a current item. After the remove operation, the current item is the item before the removed
		// item.
		// @returns the item which was just removed.
		ListEntry* Remove( )
		{
			Validate();

			ListEntry* RemovedItem = GetCurrent();
			assert( RemovedItem != NULL );
			assert( List->Count > 0 );

			List->Count--;

			if( RemovedItem->Previous == NULL )
			{
				// If the previous item was null, that means we're removing the head of the list.
				assert( List->Head == RemovedItem );
				// Assign the new head
				List->Head = RemovedItem->Next;

				if( List->Head == NULL )
				{
					// We've removed the only item in the list
					assert( List->Count == 0 );

					List->Tail = NULL; 

					// Set up the "empty list" state
					Finger = NULL;
					IsPastEnd = TRUE;
					IsPastStart = TRUE;

					return RemovedItem;
				}
				else
				{
					// Move to just before the item
					Finger = RemovedItem->Next;
					Finger->Previous = NULL;
					IsPastStart = true;
				}
			}
			else
			{
				// Move to the previous item
				Finger = RemovedItem->Previous;

				// Unlink the removed item
				Finger->Next = RemovedItem->Next;
			}

			// The forward chain has now been modified, update the backward chain accordingly

			if( Finger->Next == NULL )
			{
				// We've ended up removing the last item.
				List->Tail = Finger;
			}
			else
			{
				// Restore the backward link
				Finger->Next->Previous = Finger;
			}

			Validate();
			return RemovedItem;
		}

		void InsertBefore( ListEntry* NewEntry )
		{
			assert( NewEntry != NULL );
			Validate();

			if( IsPastStart && IsPastEnd )
			{
				// we're inserting an item into an empty list
				assert( List->Count == 0 );

				List->Head = NewEntry;
				List->Tail = NewEntry;

				NewEntry->Next = NULL;
				NewEntry->Previous = NULL;
				
				Finger = NewEntry;
				IsPastStart = FALSE;
				IsPastEnd = TRUE;
				List->Count++;
				Validate();
			}
			else if( IsPastEnd )
			{
				// Insert the item at the end
				assert( List->Count > 0 );
				assert( List->Tail == Finger );

				NewEntry->Previous = Finger;
				NewEntry->Next = NULL;

				Finger->Next = NewEntry;
				Finger = NewEntry;
				List->Tail = NewEntry;
				List->Count++;
				Validate();
			}
			else 
			{
				assert( List->Count > 0 );
				assert( !IsPastStart ); // Can't add an entry before the stub iterator position


				ListEntry* Current = GetCurrent();

				// Link up the new entry
				NewEntry->Previous = Current->Previous;
				NewEntry->Next = Current;

				if( Current->Previous == NULL )
				{
					assert( List->Head == Current );
					List->Head = NewEntry;
				}
				else
				{
					Current->Previous->Next = NewEntry;
				}

				Current->Previous = NewEntry;
				List->Count++;
				Validate();
			}
		}

		void InsertAfter( ListEntry* NewEntry )
		{
			assert( NewEntry != NULL );
			Validate();

			if( IsPastStart && IsPastEnd )
			{
				// we're inserting an item into an empty list
				assert( List->Count == 0 );

				List->Head = NewEntry;
				List->Tail = NewEntry;

				NewEntry->Next = NULL;
				NewEntry->Previous = NULL;

				Finger = NewEntry;
				IsPastEnd = FALSE;
				IsPastStart = TRUE;
				List->Count++;
				Validate();
			}
			else if( IsPastStart )
			{
				// Insert the item at the end
				assert( List->Count > 0 );
				assert( List->Head == Finger );

				NewEntry->Next = Finger;
				NewEntry->Previous = NULL;

				Finger->Previous = NewEntry;
				Finger = NewEntry;
				List->Head = NewEntry;
				List->Count++;
				Validate();
			}
			else 
			{
				assert( List->Count > 0 );
				assert( !IsPastEnd ); // Can't add an entry before the stub iterator position

				ListEntry* Current = GetCurrent();

				// Link up the new entry
				NewEntry->Next = Current->Next;
				NewEntry->Previous = Current;

				if( Current->Next == NULL )
				{
					assert( List->Tail == Current );
					List->Tail = NewEntry;
				}
				else
				{
					Current->Next->Previous = NewEntry;
				}

				Current->Next = NewEntry;
				List->Count++;
				Validate();
			}
		}

		void Validate()
		{

			if( Finger == NULL )
			{
				assert( List->Tail == NULL );
				assert( List->Head == NULL );
				assert( List->Count == 0 );
				assert( IsPastEnd );
				assert( IsPastStart );
			}
			else
			{
				assert( List->Head->Previous == NULL );
				assert( List->Tail->Next == NULL );

				int c = 0;

				bool FoundFinger = FALSE;

				for( ListEntry* it = List->Head; it != NULL; it = it->Next )
				{
					if( it->Previous == NULL )
					{
						assert( List->Head == it );
					}
					else
					{
						assert( it->Previous->Next == it );
					}

					if( it->Next == NULL )
					{
						assert( List->Tail == it );
					}
					else
					{
						assert( it->Next->Previous == it );
					}

					if( it == Finger )
					{
						assert( !FoundFinger );
						FoundFinger = TRUE;
					}
					c++;
				}
				assert( List->Count == c );
				assert(FoundFinger);
			}
		}

	};

public:
	DoublyLinkedList()
		: Head( NULL )
		, Count( 0 )
	{}

	INT GetCount() const
	{
		return Count;
	}

	Iterator GetHead()
	{
		return Iterator( *this, Head );
	}

	Iterator GetTail()
	{
		return Iterator( *this, Tail );
	}

	/// Returns whether or not the provided item is in the list. This is an O(n) operation.
	/// @param Item		The item queried. Must be an entry in the list
	/// @return			TRUE if the item is in the list.
	bool Contains( ListEntry* Item ) const
	{
		if( Item != NULL )
		{

			ListEntry* Finger = Head;
			while( Finger != 0 )
			{
				if( Finger == Item )
				{
					return true;
				}

				if( Finger->Next == NULL )
				{
					assert( Finger == Tail );
				}
				Finger = Finger->Next;
			}
		}

		return false;
	}
};

}
}